/* 
 *
 * Electric(tm) VLSI Design System
 *
 * File: BitmapTraverser.scala
 * Written by: Daniel Schmidt
 * 
 * This code has been developed at the Karlsruhe Institute of Technology (KIT), Germany, 
 * as part of the course "Multicore Programming in Practice: Tools, Models, and Languages".
 * Contact instructor: Dr. Victor Pankratius (pankratius@ipd.uka.de)
 *
 * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
 *
 * Electric(tm) is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Electric(tm) is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Electric(tm); see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, Mass 02111-1307, USA.
 */
package com.sun.electric.plugins.minarea.mk01
import scala.actors.Actor
import java.util.BitSet
import com.sun.electric.api.minarea.geometry.Point
import scala.collection.mutable.Queue
import scala.collection.mutable.Stack
import scala.collection.mutable.HashSet
import scala.collection.mutable.LinkedList
import java.util.ArrayList
import com.sun.electric.api.minarea.ErrorLogger


class BitmapTraverser(minAreaCheckerImpl: MinAreaCheckerImplementation, 
    threadNr : Int, 
    start: Int, 
    end: Int, 
    bitMap: Array[BitSet], 
    indexToXCoordinate: Array[Int],
    indexToYCoordinate: Array[Int],
    leftBorder : BitSet,
    rightBorder : BitSet,
    rightTraverser: BitmapTraverser) extends Actor {

  override def act() = {
      
    var polyAreas = new ArrayList[MarkedArea]
    var stack = new Stack[Point]
    var size: Long = 0
    
    var counter = start

    def calculateDistance(x: Int, y: Int): Long = {
      val w: Long = indexToXCoordinate(x + 1) - indexToXCoordinate(x)
      val h: Long = indexToYCoordinate(y + 1) - indexToYCoordinate(y)
      bitMap(x).clear(y)
      val p = new Point(x, y)
      stack.push(p)
      w * h
    }   
    
    /*
     * For each bitset within this plot, search any set bit and build up the
     * whole area starting from this bit recursively. 
     */
    while (counter < bitMap.length && counter <= end) {
      
      var y = bitMap(counter).nextSetBit(0)
      while (y >= 0 && y < indexToYCoordinate.length) {
        
          var area : MarkedArea = new MarkedArea()
          var upperRight : Point = new Point(counter, y)
          size += calculateDistance(counter, y)
          
          //while there are unchecked points within the current area
          while (!stack.isEmpty) {
            val p = stack.pop
            
            //actualize connections to left if the left bit is set and is out of this area
            if (p.getX() - 1 >= 0 && p.getX() - 1 < start) {
              if(leftBorder.get(p.getY)) {
                area.addConnectionsToLeft(p.getY())
              }
            } 
            //actualize connections to right if the right bit is set and is out of this area
            if(p.getX() + 1 < bitMap.length && p.getX() + 1 > end) {
              if(rightBorder.get(p.getY)) {
	            area.addConnectionsToRight(p.getY())
              }
            }

            /*
             * if the right bit is set, calculate the area, add it to this area and put the
             * corresponding point to the stack. In this case, the most upper right point
             * has to be refreshed (may have changed)
             */
            if (p.getX() + 1 < bitMap.length && p.getX + 1 <= end && bitMap(p.getX + 1).get(p.getY)) {
              size += calculateDistance(p.getX + 1, p.getY)
              upperRight = determineUpperRight(upperRight, new Point(p.getX + 1, p.getY))
            }
            /*
             * if the upper bit is set, calculate the area, add it to this area and put the
             * corresponding point to the stack. In this case, the most upper right point
             * has to be refreshed (may have changed)
             */
            if (p.getY + 1 < indexToYCoordinate.length && bitMap(p.getX).get(p.getY + 1)) {
              size += calculateDistance(p.getX, p.getY + 1)
              upperRight = determineUpperRight(upperRight, new Point(p.getX, p.getY + 1))
            }
            /*
             * if the upper bit is set, calculate the area, add it to this area and put the
             * corresponding point to the stack. 
             */
            if (p.getX - 1 >= start && bitMap(p.getX - 1).get(p.getY)) {
              size += calculateDistance(p.getX - 1, p.getY)
            }
            /*
             * if the bit beneath is set, calculate the area, add it to this area and put the
             * corresponding point to the stack. 
             */
            if (p.getY - 1 >= 0 && bitMap(p.getX).get(p.getY - 1)) {
              size += calculateDistance(p.getX, p.getY - 1)
            }
          }
          
          /*
           * Finally the resulting size of the area and the most upper right point can be set
           * to the checked area and the area can be stored in a list 
           */
          area.addSize(size)
          area.setUpperRight(upperRight)
          polyAreas.add(area)
          
          //new area -> clear size
          size = 0
          //search for the next set bit
          y = bitMap(counter).nextSetBit(0)
      }
      counter += 1
    }
    
    /*
     * After each actor has worked through his own area, it has to wait for the result
     * of its left neighbor and handle it in a proper way.
     */
    var results = new ArrayList[MarkedArea]
    if (threadNr > 0) {
      var totalArea = 0L
      var linkedSets = new ArrayList[ArrayList[MarkedArea]]()
      
      receive {
        case areaFromLeft: ArrayList[MarkedArea] =>
          
            //Build up all correlation components by traversing
            while(!areaFromLeft.isEmpty()) {
              var root = areaFromLeft.remove(0)
        	  root.setSide(true)
        	  linkedSets.add(travers(root, areaFromLeft, polyAreas, false))
            }
        	if(!polyAreas.isEmpty()) {
        	  val it : java.util.Iterator[MarkedArea] = polyAreas.iterator()
        	  while(it.hasNext()) {
        	    val single = new ArrayList[MarkedArea]()
        	    val area = it.next()
        	    area.setSide(false)
        	    single.add(area)
        	    linkedSets.add(single)
        	  }
        	}
        	
        	//Merge the resulting correlation components to one single area in each case
        	val it : java.util.Iterator[ArrayList[MarkedArea]] = linkedSets.iterator()
        	while(it.hasNext()) {
        	  results.add(merge(it.next()))
        	}
          
      }
    } else {
      results.addAll(polyAreas)
    }
    
    /*
     * Iterate through the merged areas and look after those without any connections to right
     * neighbors. Those are areas that have already been completed and may be compared
     * against the specified minimum area. If the size of the area is beneath the minArea,
     * report violation.
     */
    val it : java.util.Iterator[MarkedArea] = results.iterator()
    while(it.hasNext()) {
      val area = it.next()
      if(area.getConnectionsToRight().size == 0) {
        it.remove()
        if(area.getSize() < minAreaCheckerImpl.getMinArea()) {
        
        	minAreaCheckerImpl.getErrorLogger().reportMinAreaViolation(area.getSize(), 
        			indexToXCoordinate(area.getUpperRight().getX() + 1),
        			indexToYCoordinate(area.getUpperRight().getY() + 1), 
        			null)
        }
      }
    }

    //If there is a right neighbor, send the results to him
    if (rightTraverser != null) {
      rightTraverser ! results
    } else {
    	minAreaCheckerImpl.setFinished()
    }
    exit()
  }
  
  /**
   * Traverses through the lists left and right via the Depth-First Search starting from
   * the given area. During traversal connected areas get collected in a list, so that all
   * correlation components may be merged in a further step.
   * 
   * @return the list of all correlation components
   */
  def travers(area : MarkedArea, left : ArrayList[MarkedArea], right : ArrayList[MarkedArea], 
      turn : Boolean) : ArrayList[MarkedArea] = {
    var linked = new ArrayList[MarkedArea]()
    linked.add(area)
    var it : java.util.Iterator[MarkedArea] = null
    if(turn) {
      it = left.iterator()
      while(it.hasNext()) {
        val next = it.next()
        next.setSide(true)
        
        if(isConnected(next, area)) {
          it.remove()
          linked.addAll(travers(next, left, right, !turn))
          it = left.iterator()
        }
      }
    } else {
      it = right.iterator()
      while(it.hasNext()) {
        val next = it.next()
        next.setSide(false)
        
        if(isConnected(area, next)) {
          it.remove()
          linked.addAll(travers(next, left, right, !turn))
          it = right.iterator()
        }
      }
    }
    
    linked
  }

  /**
   * Determines whether the leftArea is connected to the rightArea. Therefore all
   * connectionsToRight of the leftArea are compared against the connectionsToLeft
   * from the rightArea.
   * 
   * @return true, if both areas contain at least one connection point, false otherwise
   */
  def isConnected(leftArea : MarkedArea, rightArea : MarkedArea) : Boolean = {
    for(connector <- leftArea.getConnectionsToRight()) {
      if(rightArea.getConnectionsToLeft().contains(connector)) {
        return true
      }
    }
    return false
  }
  
  /**
   * Merges all specified MarkedAreas to one single area in the following way:
   * 
   * 1. add the sizes of each area
   * 2. combine all connectionsToLeft of each area marked as left side
   * 3. combine all connectionsToRight of each area marked as right side
   * 4. determine the most upper right point
   * 
   */
  def merge(listOfAreas : ArrayList[MarkedArea]) : MarkedArea = {
    var result = new MarkedArea()
    
    val it : java.util.Iterator[MarkedArea] = listOfAreas.iterator()
    while(it.hasNext()) {
      val area : MarkedArea = it.next()
      result.addSize(area.getSize())

      if (area.isLeftSide()) {
        for (x <- area.getConnectionsToLeft()) {
          result.addConnectionsToLeft(x)
        }
      } else if (area.isRightSide()) {
        for (y <- area.getConnectionsToRight()) {
          result.addConnectionsToRight(y)
        }
        result.setUpperRight(area.getUpperRight())
      }
    }

    result
  }
  
  /**
   * Determines which point is the more upper right one and returns it.
   * 
   * @return the more upper right point
   */
  def determineUpperRight(p1 : Point, p2 : Point) : Point = {
    if(p1.getX() > p2.getX()) {
      p1
    } else if(p1.getX() == p2.getX()) {
      if(p1.getY() > p2.getY()) {
        p1
      } else {
        p2
      }
    } else {
      p2
    }
  }

  /**
   * MarkedArea represents one area within the bitmap. It has a size, connections
   * to left and right areas, is itself declared as a left or right side and contains
   * its most upper right point.
   */
  class MarkedArea {
    
    var size: Long = 0L
    var connectionsToLeft = HashSet[Int]()
    var connectionsToRight = HashSet[Int]()
    var side : Boolean = true
    var upperRight : Point = null

    def addConnectionsToLeft(left : Int) = {
      connectionsToLeft = connectionsToLeft.+=(left)
    }

    def addConnectionsToRight(right : Int) = {
      connectionsToRight = connectionsToRight.+=(right) 
    }
    
    def addSize(toAdd: Long) = {
      size += toAdd
    }
    
    def setSide(s : Boolean) = {
      side = s
    }
    
    def setUpperRight(p : Point) = {
      if(upperRight == null) {
        upperRight = p
      } else {
        upperRight = determineUpperRight(upperRight, p)
      }
    }
    
    def isLeftSide() = side
    
    def isRightSide() = !side
    
    def getUpperRight() = upperRight

    def getConnectionsToLeft() = connectionsToLeft
    
    def getConnectionsToRight() = connectionsToRight
    
    def getSize() = size
  }
}